package j2024.j202407;

import java.util.PriorityQueue;

public class j0709 {

}
class MedianFinder {
    PriorityQueue<Integer> Lheap;
    PriorityQueue<Integer> Rheap;
    public MedianFinder() {
        Lheap = new PriorityQueue<>((a,b)->b-a);//左半大根堆
        Rheap = new PriorityQueue<>();//右半小根堆
    }

    public void addNum(int num) {
        if(Lheap.size()==Rheap.size()){
            if(Lheap.isEmpty() || num<=Lheap.peek()){
                Lheap.offer(num);
            }else{
                Rheap.offer(num);
                int tmp = Rheap.poll();
                Lheap.offer(tmp);
            }
        }else if (Lheap.size()>Rheap.size()){
            if(num<=Lheap.peek()){
                Lheap.offer(num);
                int tmp = Lheap.poll();
                Rheap.offer(tmp);
            }else{
                Rheap.offer(num);
            }
        }
    }

    public double findMedian() {
        if(Lheap.size()>Rheap.size()){
            return Lheap.peek();
        }else {
            return (Lheap.peek()+Rheap.peek())/2.0;
        }
    }
}
